// 此题目要求使用两个队列来实现栈
// 栈的功能为先入后出,于队列的功能向违背(先入先出)
// 但是,使用两个队列,将除队尾最后一个数据全部存入另外一个队列里面,这样子队尾的数据就变成队头了,可以取出
// 只要循环往复,即可实现栈的功能

typedef int QDataType ;

typedef struct QueueNode
{
    
    QDataType data ;

    struct QueueNode* next ;

} QueueNode ;

// 队列的结构

typedef struct Queue
{

    QueueNode* phead ;

    QueueNode* ptail ;

    // int size ; // 获取队伍有效数据的个数(方法1)

} Queue ;

void QueueInit (Queue* pq)
{

    assert (pq) ;

    pq -> phead = pq -> ptail = NULL ;

    // pq -> size = 0 ; // 初始数据为0

}

// 队列的销毁

void QueueDestory (Queue* pq)
{

    assert (pq) ;

    QueueNode* pcur = pq -> phead ;

    while (pcur) // 一直销毁直到为空
    {

        QueueNode* next = pcur -> next ;

        free (pcur) ;

        pcur = next ;

    }

    pq -> phead = pq -> ptail = NULL ;

    // pq -> size = 0 // 重置有效元素个数

}

// 队列判空

bool QueueEmpty (Queue* pq)
{

    assert (pq) ;

    return pq -> phead == NULL ;

}

// 入队---队尾

void QueuePush (Queue* pq , QDataType x)
{

    assert (pq) ;

    QueueNode* newnode = (QueueNode*) malloc (sizeof (QueueNode)) ;

    if (newnode == NULL)
    {

        perror ("malloc fail!") ;

        exit (1) ;

    }

    newnode -> data = x ;

    newnode -> next = NULL ;

    // 队列为空

    if (pq -> phead == NULL)
    {

        pq -> phead = pq -> ptail = newnode ;

    }

    else
    {

        // 队列非空

        pq -> ptail -> next = newnode ;

        pq -> ptail = pq -> ptail -> next ;

    }

    // pq -> size++ ; // 有效数据加1

}

// 出队---队头

void QueuePop (Queue* pq)
{

    assert (!QueueEmpty (pq)) ;

    // 只有一个节点,phead和ptail都置为空

    if (pq -> phead == pq -> ptail)
    {

        free (pq -> phead) ;

        pq -> phead = pq -> ptail = NULL ;

    }

    else
    {

        QueueNode* next = pq -> phead -> next ;

        free (pq -> phead) ;

        pq -> phead = next ;

    }

    // pq -> size-- // 有效数据减1

}

// 取队头数据

QDataType QueueFront (Queue* pq)
{

    assert (!QueueEmpty (pq)) ; // 队列不为空才能取数据

    return pq -> phead -> data ;

}

// 取队尾数据

QDataType QueueBack (Queue* pq)
{

    assert (!QueueEmpty (pq)) ;

    return pq -> ptail -> data ;

}


// 取队列有效元素个数

int QueueSize (Queue* pq)
{

    assert (pq) ;

    // 第一种方式: 遍历链表---适用于不会频繁调用队列有效个数的场景

    QueueNode* pcur = pq -> phead ;

    int size = 0 ;

    while (pcur)
    {

        size++ ;

        pcur = pcur -> next ;

    }

    return size ;

    // 第二种方式: 在结构体设置size变量,在调用的时候自增减---适用于需要频繁调用队列有效个数的场景

    // return size ;
    
}

typedef struct 
{

    Queue q1 ;

    Queue q2 ;
    
} MyStack;

// 初始化

MyStack* myStackCreate() 
{

    MyStack* pst = (MyStack*) malloc (sizeof (MyStack)) ;

    QueueInit (&pst -> q1) ;

    QueueInit (&pst -> q2) ;

    return pst ;
    
}

void myStackPush(MyStack* obj, int x) 
{

    // 往不为空的队列中插入数据(一开始往q1或者q2插入数据都行)

    if (!QueueEmpty (&obj -> q1))
    {

        QueuePush (&obj -> q1 , x) ;

    }

    else
    {

        QueuePush (&obj -> q2 , x) ;

    }

}

// 将不为空的队列中前size - 1个数据挪到另一个队列中
// 再将最后一个数据出队列

int myStackPop(MyStack* obj) 
{

    Queue* empty = &obj -> q1 ;

    Queue* noempty = &obj -> q2 ;

    if (QueueEmpty (&obj -> q2))
    {

        empty = &obj -> q2 ;

        noempty = &obj -> q1 ;

    }

    while (QueueSize (noempty) > 1)
    {

        QueuePush (empty , noempty -> phead -> data) ;

        QueuePop (noempty) ;

    }

    int top = QueueFront (noempty) ;

    QueuePop (noempty) ;

    return top ;
    
}

// 取栈顶

int myStackTop(MyStack* obj) 
{

    // 找不为空队列中的队尾数据

    if (!QueueEmpty (&obj -> q1))
    {

        return QueueBack (&obj -> q1) ;

    }

    else
    {

        return QueueBack (&obj -> q2) ;

    }
    
}

bool myStackEmpty(MyStack* obj) 
{

    return QueueEmpty (&obj -> q1) && QueueEmpty (&obj -> q2) ;
    
}

// 销毁

void myStackFree(MyStack* obj) 
{

    QueueDestory (&obj -> q1) ;

    QueueDestory (&obj -> q2) ;

    free (obj) ;

    obj = NULL ;
    
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/